package com.julius.design.suanfa.search;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author julius
 * @date 2021-11-05 下午 3:15
 * <p>
 *      地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，
 *      它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。
 *      例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 *
 *      链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
 * </p>
 */
public class MatrixMoveCount {


    /**
     * 错误解法，忽略了每次机器人只能移动一次（上下左右）
     * @param m
     * @param n
     * @param k
     * @return
     */
    public int movingCount(int m, int n, int k) {
        //深度优先搜索，经历过的位置需要记录，去重
        int count = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(twoNum(i,j) <= k){
                    count++;
                }else{
                    n--;
                }
            }
        }
        return count;
    }
    //计算位置各个位数之和
    public int twoNum(int i,int j){
        if(i > 10){
            int temp = i;
            int sum = 0;
            while(temp != 0){
                sum+=temp%10;
                temp /= 10;
            }
            i = sum;
        }

        if(j > 10){
            int temp = i;
            int sum = 0;
            while(temp != 0){
                sum+=temp%10;
                temp/=10;
            }
            j = sum;
        }
        return i+j;
    }


    /* *********************************************** DFS 深度优先搜索 ******************************************** */

    /**
     * 机器人移动步数
     * 深度优先遍历 （递归）
     *
     *
     * @param m
     * @param n
     * @param k
     * @return
     */
    public int moveCountDfs(int m,int n ,int k){
        return dfs(m,n,0,0,k,new boolean[m][n]);
    }


    /**
     * 深度优先遍历
     * @param i 遍历行索引
     * @param j 遍历列索引
     * @param m 总行数
     * @param n 总列数
     * @param k
     * @param visited 已经访问的位置
     * @return
     */
    public int dfs(int m ,int n,int i,int j,int k,boolean[][] visited){
        //临界条件
        if(i >= m || j >= n || k < get(i)+get(j) || visited[i][j]){
            return 0;
        }
        //标记当前位置已经被访问
        visited[i][j] = true;
        //当前位置
        int cur = 1;

        //当前位置的下方
        int curDown = dfs(m,n,i+1,j,k,visited);

        //当前位置的右方
        int curRight = dfs(m,n,i,j+1,k,visited);

        //返回数据
        return cur+curDown+curRight;

    }
    /**
     * 计算各个位数之和
     * @param value
     * @return
     */
    public int get(int value){
        int sum = 0;
        while (value != 0){
            sum+=value%10;
            value = value / 10;
        }
        return sum;
    }

    /* ****************************************** BFS  广度优先搜索 ************************************************ */


    /**
     *  使用 BFS 搜索
     *  一般使用队列辅助完成
     *
     * @param m
     * @param n
     * @param k
     * @return
     */
    public int moveCountBfs(int m ,int n ,int k){
        if(k == 0){
            return 1;
        }
        //标记节点是否刚被访问
        boolean[][] visited = new boolean[m][n];
        //使用队列存储被访问的节点 顺序是矩阵中  当前节点，当前节点的下方节点，当前节点的右方节点
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0,0});

        int ans = 0;
        while(!queue.isEmpty()){
            //弹出队列的首节点
            int[] cur = queue.poll();
            int i = cur[0],j = cur[1];

            //越界
            if(i >= m || j >= n){
                continue;
            }
            //目标数位和
            int target = get(i)+get(j);
            //不满足位置
            if(target > k || visited[i][j]){
                continue;
            }

            //满足条件，标记已经访问
            visited[i][j] = true;
            ans++;
            //加入当前节点的下方节点和右方节点
            queue.offer(new int[]{i+1,j});
            queue.offer(new int[]{i,j+1});
        }
        return ans;
    }

    public static void main(String[] args) {
        MatrixMoveCount matrixMoveCount = new MatrixMoveCount();
        System.out.println(matrixMoveCount.moveCountBfs(11,8,16));
        /**
         *       1  2  1
         *
         *       5
         *
         *       0 1 2 3 4 5 6
         *       b b b b b b a  0
         *       b b b b b a a  1
         *       b b b b a a a  2
         *       b b b a a a a  3
         *       b b a a a a a  4
         *
         */
    }
}
